contents

퍼지 파인딩(Fuzzy finding) 은 퍼지 검색(fuzzy search) 이라고도 하며, 쿼리와 정확하게 일치하는 결과가 아닌 근사적으로 일치하는 결과를 찾는 검색 기술입니다. 이는 오타, 철자 오류, 혹은 축약어에 대해 너그럽게 설계된 강력한 방법입니다.

사용자가 찾고자 하는 것의 "요점"을 파악하여, 완벽한 정확성보다는 속도와 사용자 편의성을 우선시하는 검색 방식이라고 생각할 수 있습니다.

퍼지 파인딩이 해결하는 문제

퍼지 파인딩을 이해하는 가장 좋은 방법은 다른 검색 유형과 비교하는 것입니다.

• 정확한 검색: 텍스트 편집기에서 Ctrl+F를 누를 때의 간단한 검색 방식입니다. "file_name"을 검색하면 정확히 그 문자 시퀀스만 찾습니다. "filename"이나 "filemane"을 검색하면 아무 결과도 찾지 못합니다.
• 전문 검색(Full-Text Search): Elasticsearch와 같은 데이터베이스나 검색 엔진에서 사용하는 방식입니다. 더 발전된 형태로, 텍스트를 단어(토큰)로 나누고 종종 어근을 이해합니다(예: "run"을 검색하면 "running"도 찾을 수 있음). 하지만 여전히 핵심 단어를 매칭하는 데 의존합니다.
• 퍼지 파인딩: 이는 다른 패러다임입니다. authentication_controller.rb라는 파일이 있을 때, 다음과 같이 입력하여 찾을 수 있습니다.
  • authcon (문자들의 부분 시퀀스)
  • ac.rb (초성)
  • authencontroler (오타)

퍼지 파인딩은 짧고 부정확한 입력을 기반으로 방대한 항목 목록(파일, 명령어, 연락처 등)을 빠르게 좁히는 데 탁월합니다.

작동 원리: 핵심 알고리즘 ⚙️

퍼지 파인딩은 쿼리 문자열과 각 잠재적 일치 항목 사이의 "점수" 또는 "거리"를 계산하여 작동합니다. 가장 좋은 점수를 받은 항목이 순위가 가장 높게 매겨집니다. 여기에는 두 가지 주요 접근 방식이 있습니다.

1. 편집 거리 (예: 레벤슈타인 거리)

두 문자열이 얼마나 다른지를 측정하는 고전적인 접근 방식입니다.

• 개념: 레벤슈타인 거리는 한 문자열을 다른 문자열로 바꾸는 데 필요한 최소한의 단일 문자 편집(삽입, 삭제, 또는 대체) 횟수입니다.
• 예시: "saturday"를 "sunday"로 바꾸기 위해
  1. saturday -> s**u**turday ('a'를 'u'로 대체)
  2. suturday -> sun**n**rday ('t'를 'n'으로 대체)
  3. sunrday -> sunday ('r' 삭제)
  • 레벤슈타인 거리는 3입니다.
• 사용 방식: 이 방법을 사용하는 퍼지 검색은 쿼리와의 편집 거리가 가장 낮은 항목들을 반환합니다. 오타를 수정하는 데 매우 효과적입니다.

2. 점수 기반 부분 문자열 매칭 (현대적인 접근 방식)

이것은 fzf나 VS Code와 같은 코드 편집기에서 사용되는 대부분의 현대적인 퍼지 파인더가 사용하는 알고리즘입니다. 오류 수정보다는 약어에 대한 최상의 일치 항목을 찾는 데 더 중점을 둡니다.

• 개념: 쿼리의 문자들이 대상 문자열에 부분 문자열(subsequence) 로 나타나는지 확인합니다. 즉, 문자들이 같은 순서로 나타나지만, 반드시 연속적일 필요는 없습니다.
• 점수 시스템: 부분 문자열을 찾는 것은 쉽습니다. 마법은 점수 매기기에 있습니다. 좋은 퍼지 파인더는 일치 항목의 순위를 직관적으로 매기기 위해 일련의 휴리스틱을 사용합니다. 다음과 같은 경우에 더 높은 점수를 받습니다.
  • 연속적인 일치: **a**...**u**...보다 **au**thentication의 **au**th가 더 좋습니다.
  • 단어의 시작 부분과 일치: ar**c**h...보다 **a**uth_**c**ontroller (초성 일치)가 훌륭한 일치입니다.
  • 구분자 뒤의 일치: _**c**ontroller가 좋습니다.
  • 간격이 작을 때: 건너뛰는 문자에 대한 페널티는 간격의 크기가 커질수록 증가합니다.

예시:

• 쿼리: ac
• 잠재적 일치 항목:
  1. **a**pp_**c**ontroller.rb (높은 점수: 구분자 뒤의 초성 일치)
  2. **ac**count.rb (높은 점수: 시작 부분의 연속 일치)
  3. archiver/c**a**che.rb (낮은 점수: 간격이 크고, 단어 경계가 아님)

이 알고리즘은 본질적으로 대상 문자열을 통과하는 쿼리 문자에 대한 최상의 "경로"를 찾아 그 경로에 점수를 매기는 방식입니다.

일반적인 사용 사례 ✅

퍼지 파인딩은 사용자가 긴 목록에서 매우 빠르게 항목을 선택해야 하는 애플리케이션에서 가장 인기가 있습니다.

• 개발자 도구: 이것이 퍼지 파인딩의 킬러 애플리케이션입니다.
  • 코드 편집기의 "파일로 이동" 기능 (VS Code, Sublime Text 등).
  • 셸 히스토리, 파일 또는 프로세스를 검색하기 위한 fzf(퍼지 파인더)와 같은 명령줄 도구.
• 애플리케이션 실행기: macOS의 Alfred나 Windows 시작 메뉴 검색과 같은 도구는 퍼지 로직을 사용하여 앱과 파일을 찾습니다.
• 검색창: 일부 웹사이트는 제품이나 기사에 대한 사용자 오타를 처리하기 위해 퍼지 검색을 사용합니다.
• 연락처 목록: 초성이나 잘못된 이름으로 연락처를 검색합니다.

결론적으로, 퍼지 파인딩은 정확성보다 속도와 편의성을 우선시하는 사용자 중심의 검색 방법입니다. 영리한 점수 알고리즘을 사용하여 사용자가 최소한의, 그리고 종종 부정확한 키 입력으로 원하는 것을 찾을 수 있게 해주어, 현대적인 생산성을 위한 필수 도구가 되었습니다.

references